1. Field of the Invention
The present invention relates to an IP address lookup method and hardware architecture using hashing, and more particularly to an IP address lookup method and hardware architecture for classifying prefixes based on the prefix lengths, constructing separate tables corresponding to the classified prefix lengths of the IP address, performing an IP address lookup process on the tables by applying hash functions in parallel, and selecting entries having the longest-matched-prefix among the prefix-matched entries.
2. Description of the Related Art
One of the most challenging tasks that should be performed in the Internet routers widely used in the world is to accurately forward a received packet to its destination. In order to implement the task, every router comprises a forwarding table. Information on next hop addresses and output ports used to access the destination are obtained by using the forwarding table. When the packet is received, the router performs a process for referring to the forwarding table by using the Network Part of the destination IP addresses of the received packet as a key. This is called an address lookup process. The Network Part used for the address lookup process is called a prefix.
Conventionally, there is a classful addressing scheme for the IP address lookup process. In the scheme, the lengths of the prefixes of the IP address are fixed in 8, 16, or 24 bits. Since the lengths of the prefixes are fixed, the class-ful addressing scheme has a problem in that some of the IP addresses are wasted. In addition, the scheme has another problem in that, as the kinds of the networks are increasing, the size of the forwarding table has to exponentially increase.
In order to solve the problems of the classful addressing scheme, there is proposed a classless inter-domain routing (CIDR) scheme. In the CIDR scheme, since the lengths of the prefixes are not fixed, it is possible to prevent the IP addresses from wasting. In addition, since IP addresses can be aggregated, it is possible to prevent the size of the forwarding table from rapidly increasing. However, the CIDR scheme has a problem in that the so-called longest prefix matching process has to be performed. Since an incoming packet does not carry information on the prefix length of its own final network, a process has to be performed to search an entry having the longest prefix among the entries of the forwarding table having prefixes matched with the prefix of the address of the incoming packet. In other words, various IP address lookup processes conventionally used for the exact matching cannot be adapted to the longest prefix matching scheme. As a result, there are generated bottlenecks at the router.
There are several criteria used to estimate performance of an IP address lookup architecture. The first criterion is the number of memory accesses. Since the rapid IP address lookup is required in order to cope with the increase in the link speed, it is important to reduce the number of memory accesses, which may result in the most principal factor of overhead. The second criterion is the memory size. For example, in case of a backbone router, as the number of networks connected to the backbone router is exponentially increasing, the number of entries that should be stored in the forwarding table is also rapidly increasing. Therefore, it is necessary to effectively store the increasing entries in the memory, so that the IP address lookup process can be efficiently performed. As a result, the memory size becomes one of the principal factors in the IP address lookup process. The other criteria include table updatability for adding new prefixes or removing unused prefixes in the forwarding and an expandability to the IPv6 having a 128-bit address system.
Recently, various approaches for IP address lookup in the Internet router have been developed. The various approaches for IP address lookup may be classified as follows.
A first approach is an IP address lookup process using a content addressable memory (CAM). This approach has been used for an actual switch or router. The input IP address is directly compared with all the prefixes stored in the content addressable memory, so that the speed of the IP address lookup process is very high. However, there is a problem in that the technique associated with the content addressable memory has not coped with the rapidly increasing number of prefixes used for the router. In other words, in comparison with a RAM having the same memory size, the content addressable memory stores a very small number of prefixes. In addition, the cost of the content addressable memory is too high. Therefore, it is difficult to implement the content addressable memory for storing several ten-thousands of prefixes. In addition, it is difficult to embed the even implemented content addressable memory in a chip designed for the IP address lookup process. Therefore, it is difficult to apply the technique associated with the content addressable memory to the forwarding tables of a backbone router having several ten-thousands of entries and the IPv6 having addresses of 128-bit length.
A second approach is an IP address lookup process based on a Trie structure. The Trie structure is the most well-known data structure based on a tree which represents relationship between prefixes very well. In the Trie structure, every prefixes is located at a single node in the tree, which defines a path from a root node. Many researches have been made on architectures of storing the Trie structure in a memory and the associated IP address lookup schemes. However, the second approach has a problem in that the memory is wasted since prefix-unassigned internal nodes are stored. In addition, there is a problem in that W times of memory accesses are performed assuming that W is the height of the tree. In addition, it is difficult to perform an updating process to add new prefixes and remove unused prefixes.
There is proposed a Trie structure capable of reducing the number of memory accesses by using prefix expansion. In the Trie structure, a set of D prefix lengths is expanded into another set of L prefix lengths (D>L), so that some portion of prefix lengths can be expanded to reduce the number of different sets of the prefix lengths. In addition, there is proposed another Trie structure capable of performing a primary searching process in a memory having 224 entries obtained by expanding the shorter-than-24 prefix lengths to 24 prefix lengths. In the Trie structure, when the incoming address has a longer-than-24 prefix length, the searching process is performed on another table storing the remaining longer-than-24 prefix lengths. Even though the maximum number of memory accesses is advantageously only 2, the Trie structure has a problem in that a large-sized memory of 33 Mbytes is used to store 224 entries.
On the other hand, there is proposed another Trie structure where a forwarding table is constructed with a memory having 216 entries obtained by expanding the shorter-than-16 prefix lengths to 16 prefix lengths. In the Trie structure, when the incoming address has longer-than-16 prefix lengths, a process for searching the longer-than-16 prefixes lengths is performed along sub-trees. Although it has an advantage in the smaller memory can be used compared with the aforementioned architectures, the IP address lookup architecture using the Trie structure has a problem in that the amount of pre-processing increases and the updating process is difficult.
A third approach is an IP address lookup process using a binary search combined with a hashing applied to prefixes of the same length. The hashing has been popularly used for Layer-2 address lookup which requires exact matching. However, the binary searching combined hashing scheme has a problem in that a pure binary searching process can not apply. In other words, even in a case where the entry searched by the hashing does not include a prefix, a large number of markers indicating that a longer prefix exists have to be stored due to the longest prefix matching characteristics of the IP address. Therefore, there is a problem in that overhead is induced to calculate the large number of markers in advance. In addition, since it is based on an assumption that a perfect hash function can be rapidly obtained with respect to a given prefix distribution, the binary searching combined hashing scheme is not practical.
In order to solve the problem that it takes too long time to search the perfect hash function, there is still another scheme for searching multiple hash functions in accordance with the data distribution instead of the perfect hash function. Recently, some research has been made to implement a semi-perfect hashing scheme by using the multiple hash functions and generating tables for the corresponding hash functions.